//documentation http://docs.scala-lang.org/style/scaladoc.html
package com.cs51.seam

import java.awt.image.BufferedImage
import scala.collection.immutable.HashMap
import java.io.File
import java.awt.Color


/**
 * this object provides the ability to determine seams based on the dynamic programming model
 * suggested for seam carving
 */
object DynamicProgramming {
	
	/**
	 * isLast returns true if s is at the end
	 * 
	 * @param graph		the graph to use
	 * @param s			the seamNode to test
	 * @return			true if last
	 */
	private def isLast (graph: SeamMap, s: SeamNode) = {
	  graph.getSuccessors(s.thisItem, s.direction) match {
	    case Some(successors) =>
	      successors.center match {
		    case End() => throw new IllegalArgumentException("error with item at " + s.thisItem.x + ", " + s.thisItem.y)
		    case _ => false
		  }
	    case None => 
	      true
	  }
	}

	/**
	 * determines next min-value seam
	 * @param graph			the graph in which to calculate next seam
	 * @param avgEnergy		specifies the maximum average energy for a seam
	 * @param dir			the direction that the seam should travel
	 * @return				the SeamNode and Graph with seams removed (or none if none found)
	 */
	def getNextSeam(graph : SeamMap, avgEnergy : Double, dir: SeamDirection) : Option[(SeamMap,SeamNode,Int)] = {
		//maintain length of graph in val
		val length : Int = graph.getLength(dir)
	  
		//gets first row of nodes and transforms to seam buds
		def getFirstSeams : List[SeamNode] = {
		  (graph.getFirst(dir).map(node => new SeamNode(new Top, node, node.energy, dir)))
		}
		
		//returns which ever one is better
		def getBestSeam(s1: SeamNode, s2 :SeamNode) : SeamNode = {
		  if (s2.totalScore < s1.totalScore) s2
		  else s1
		}
		
		//transforms a previous seam and a node into a new seam
		def getSeam(nodeitem : NodeItem, parent: SeamNode) : SeamNode = {
		  nodeitem match {
		    case (node : Node) =>  new SeamNode(parent, node, node.energy + parent.totalScore, dir)
		    case _ => throw new IllegalArgumentException("node expected for nodeitem")
		  }
		}
		
		//use only if getting a node: gets a node from nodeitem or throws exception if not
		def getNode(nodeItem : NodeItem) : Node = {
		  nodeItem match {
		    case (n : Node) => n
		    case _ => throw new IllegalArgumentException("get node given an unacceptable argument of End")
		  }
		}
		
		//given a list of seams, return which ever one is the best
		def bestSeam(lst : List[SeamNode], maxScore:Double) : Option[SeamNode]  = {
		  lst.foldLeft[Option[SeamNode]](None)((prev, item) => 
		    prev match {
		      case None => 
		        if (item.totalScore <= maxScore) Some(item)
		        else None
		      case Some(s) => Some(getBestSeam(s, item))
		    })
		}
	  
		//identify seams for each consequent row
		def nextRow (prevRow : List[SeamNode], thisRow : List[SeamNode]) : List[SeamNode] = {
		  (prevRow, thisRow) match {
		    //first most column - if list taken is Nil, we are at very first.
		    case ((prevFirst::prevTl), Nil) => 
		      val succ = graph.getSuccessors(prevFirst.thisItem, dir).get
		      //seam first should be empty
		      val seamCent = getSeam(succ.center, prevFirst)
		      val seamLast = getSeam(succ.last, prevFirst)
		      nextRow(prevTl, seamCent::seamLast::Nil)
		    
		    //most instances (in the middle) - we need two items from previous to guarantee we are not on last
		    case ((prevItem::nextPrev::prevTl), (thisFirst::thisCent::Nil)) =>
		      val succ = graph.getSuccessors(prevItem.thisItem, dir).get
		      val newSeamFirst = getBestSeam(getSeam(succ.first, prevItem), thisFirst)
		      val newSeamCent = getBestSeam(getSeam(succ.center, prevItem), thisCent)
		      val newSeamLast = getSeam(succ.last, prevItem)
		      // left should be set by this point, pass it on to the next recurssion
		      newSeamFirst :: 
		    	  (nextRow(nextPrev::prevTl, newSeamCent::newSeamLast::Nil))
		    	  
		    //right most...
		    case ((prevLast::Nil), (thisFirst::thisCent::Nil)) =>
		      val succ = graph.getSuccessors(prevLast.thisItem, dir).get
		      val newSeamFirst = getBestSeam(getSeam(succ.first, prevLast), thisFirst)
		      val newSeamCent = getBestSeam(getSeam(succ.center, prevLast), thisCent)
		      newSeamFirst::newSeamCent::Nil
		      
		    case _ => throw new IllegalArgumentException("either empty or some invariant broken")
		  }
		}
		
		//recurses continuing to get seams until at last row and then returns the seams gathered
		def getLastSeams(thisRow : List[SeamNode]) : List[SeamNode] = {
		  thisRow match {
		    case front::tl =>
		      if (isLast(graph, front)) thisRow
		      else getLastSeams(nextRow(thisRow, Nil))
		    case Nil => throw new IllegalArgumentException("the length of the list is empty")
		  }
		}
		
		
		bestSeam(getLastSeams(getFirstSeams), (avgEnergy * length)) match {
		  case None => None
		  case Some(seam) => 
		    val newGraph = graph.deleteNodes(seam)
		    Some(newGraph, seam, graph.getLength(dir))
		}
	}
}




/**
 * carves up the image and provides object for solution
 * @param img				the image to be carved
 * @param maxEnergy			the maximum allowable energy to remove
 * @param vertShrinkNum		how much to shrink vertically
 * @param horzShrinkNum		how much to shrink horizontally
 * @param emeth				the energy method to use
 * @param imageEnlarge		whether or not to enlarge the image using this process
 */
class SeamCarve (img : BufferedImage, maxEnergy : Double, 
    vertShrinkNum: Int, horzShrinkNum: Int, emeth: EnergyMethod, imageEnlarge : Boolean) {

    if (vertShrinkNum < 0 || horzShrinkNum < 0) throw new IllegalArgumentException("the number of seams to remove in either direction must be a non-negative number")
	if (img.getWidth() - horzShrinkNum < SeamConstants.MIN_RESULT_IMAGE_WIDTH || img.getHeight() - vertShrinkNum < SeamConstants.MIN_RESULT_IMAGE_HEIGHT)
		throw new IllegalArgumentException("Demanded image size is outside of acceptable limits.  Please make sure image width - horizontal seams is bigger than " + 
				SeamConstants.MIN_RESULT_IMAGE_WIDTH + " and image height - vertical seams is bigger than " + SeamConstants.MIN_RESULT_IMAGE_HEIGHT)
	
    //make sure image is within proper dimensions
    if (img.getWidth() > SeamConstants.MAX_ORIG_IMAGE_WIDTH || img.getHeight() > SeamConstants.MAX_ORIG_IMAGE_HEIGHT)
    	throw new IllegalArgumentException("Original image is outside acceptable limits.  Max image size should be " + SeamConstants.MAX_ORIG_IMAGE_WIDTH +
    	    " by " + SeamConstants.MAX_ORIG_IMAGE_HEIGHT);
    
    //make sure resulting image is within max dimensions
    if (imageEnlarge) {
      if (img.getWidth() + horzShrinkNum > SeamConstants.MAX_RESULT_IMAGE_WIDTH
          || img.getHeight() + vertShrinkNum > SeamConstants.MAX_RESULT_IMAGE_HEIGHT)
    	  		throw new IllegalArgumentException("Resulting image from seam carving will be outide the dimensions of " + 
    	  		    SeamConstants.MAX_RESULT_IMAGE_WIDTH + " by " + SeamConstants.MAX_RESULT_IMAGE_HEIGHT);
    }
    else
      if (img.getWidth() - horzShrinkNum > SeamConstants.MAX_RESULT_IMAGE_WIDTH
          || img.getHeight() - vertShrinkNum > SeamConstants.MAX_RESULT_IMAGE_HEIGHT)
    	  		throw new IllegalArgumentException("Resulting image from seam carving will be outide the dimensions of " + 
    	  		    SeamConstants.MAX_RESULT_IMAGE_WIDTH + " by " + SeamConstants.MAX_RESULT_IMAGE_HEIGHT);
    
    
    
    
    
    
	/**
	 * default constructor for SeamCarve where all defaults are assumed
	 * @param img		the image to carve
	 */
	def this(img : BufferedImage) = this(img, 1,
	    (SeamConstants.SEAM_DEFAULT_MAX_VERT_PROPORTION * img.getHeight()).toInt, 
	    (SeamConstants.SEAM_DEFAULT_MAX_HORZ_PROPORTION * img.getWidth()).toInt, new EnergyMethodE1, false)
	
	
	//do some basic set up stuff
	val eget = new GetEnergy(img, emeth)
	val emap = eget.getEnergyMap
	val originalGraph = new SeamMap(emap, img)
	
	// vals for the finished graph and the reverse order of Seams - 
	// if image enlarge, gets both horizontal and vertical seams
    // if image enlarge, both revOrderSeams and revOrderSeams2 should contain values
    // otherwise, only the first two values are useful
	val (finishedGraph, revOrderSeams, revOrderSeams2) = 
	  if (imageEnlarge) {
	    //calculate vertical shrinking first (if necessary)
	    val (nextGraph, seams) = 
	      if (vertShrinkNum > 0) {
	        println("getting vertical seams...")
		    val (_, vertSeams) = getSeams(originalGraph, vertShrinkNum, 0, maxEnergy, Nil)
		    val nextGraph = originalGraph.insertNodes(vertSeams)
		    (nextGraph, vertSeams)
	      }
	      else (originalGraph, Nil)

	      //calculate horizontal shrinking second (if necessary)
  	      if (horzShrinkNum > 0) {
  	        println("getting horizontal seams...")
		    val (_, horzSeams) = getSeams(nextGraph, 0, horzShrinkNum, maxEnergy, Nil)
		    val finalgraph = nextGraph.insertNodes(horzSeams)
		    (finalgraph, seams, horzSeams)
	      }
	      else (nextGraph, seams, Nil)
	      
	  } 
    //if not doing image enlargement, just pass back results from removing seams
	  else {
	    val (graph, seams) = getSeams(originalGraph, vertShrinkNum, horzShrinkNum, maxEnergy, Nil)
	    (graph, seams, Nil)
	  }
	    
	  
	  
	
	/**
	 * recursive function that gets seams until seams are removed or maxEnergy limit is hit
	 * @param graph			the current SeamMap representing pixels remaining
	 * @param vertShrink	the current amount to shrink vertically
	 * @param horzShrink	the current amount to shrink horizontally
	 * @param maxEnergy		the maximum energy for a seam
	 * @param prevSeams		the seams currently accrued at this point in recursion
	 * @return				the finished SeamMap and list of SeamNodes representing all seams to remove
	 */
	private def getSeams(graph : SeamMap, vertShrink : Int, horzShrink : Int, maxEnergy : Double, prevSeams : List[SeamNode]) : (SeamMap, List[SeamNode]) = {
	  println("vertical seams remaining: " + vertShrink + "  horizontal seams remaining: " + horzShrink)

		((vertShrink > 0), (horzShrink > 0)) match {
		  //still need at least one of each
		  case (true, true) => 
		    //get a vertical seam (shrinking horizontally) and a horizontal seam (shrinking vertically) and compare
		  	(DynamicProgramming.getNextSeam(graph, maxEnergy, VertSeam()), 
		  	    DynamicProgramming.getNextSeam(graph, maxEnergy, HorzSeam())) match {
		  	  case (Some((horGraph, horSeam, horLength)), 
		  	      Some((vertGraph, vertSeam, vertLength))) => 
		  	        if ((vertSeam.totalScore / vertLength) < (horSeam.totalScore / horLength))
		  	          getSeams(vertGraph, (vertShrink - 1), horzShrink, maxEnergy, vertSeam::prevSeams)
		  	        else
		  	          getSeams(horGraph, vertShrink, (horzShrink - 1), maxEnergy, horSeam::prevSeams)
  		  	  case (Some((horGraph, horSeam, horLength)), None) => 
  		  	    getSeams(horGraph, vertShrink, (horzShrink - 1), maxEnergy, horSeam::prevSeams)
		  	  case (None, Some((vertGraph, vertSeam, _))) => 
		  	    getSeams(vertGraph, (vertShrink - 1), horzShrink, maxEnergy, vertSeam::prevSeams)
		  	  case (None, None) => (graph, prevSeams)
		  	}
		  //need to shrink vertically
		  case (true, false) => 
		    //just get a horizontal seam since shrinking vertically
		  	DynamicProgramming.getNextSeam(graph, maxEnergy, HorzSeam()) match {
		  	  case Some((newGraph, seam, length)) => 
		  	    getSeams(newGraph, (vertShrink - 1), horzShrink, maxEnergy, seam::prevSeams)
		  	  case None => (graph, prevSeams)
		  	}
		  //need to shrink horizontally
		  case (false, true) =>
		    //just get a vertical seam since shrinking horizontally
		  	DynamicProgramming.getNextSeam(graph, maxEnergy, VertSeam()) match {
		  	  case Some((newGraph, seam, length)) => 
		  	    getSeams(newGraph, vertShrink, (horzShrink - 1), maxEnergy, seam::prevSeams)
		  	  case None => (graph, prevSeams)
		  	}
		  //all done
		  case (false, false) => (graph, prevSeams)  
		}
	}
	
	/**
	 * gets an image representing finished product
	 * @return		the finished image
	 */ 
	def getImage : BufferedImage = {
		finishedGraph.getImage
	}
	

	/**
	 * gets animation pics based on seam carving process
	 * @return			the animation pictures
	 */
	def getAnimPics : Array[File] = {
	  println("preparing movie...")
	  val imgCopy = copyImage(img)
	  val energyPics = eget.getAnimPics
	  
      if (imageEnlarge) {
        val finalImg = getImage
	    val finalImgFiles = Utils.generateLots(Utils.imageToTempFile(finalImg), 40)
	    
        val newEnergyPics = energyPics.map(img => 
          Utils.imageToTempFile(
	          Utils.giveEdges(Utils.getImage(img), Color.black, 
	              finalImg.getHeight(), finalImg.getWidth(), Utils.ImgPosition.Center)))
	    
    	val verticalSeams = revOrderSeams.reverse
    	val horizontalSeams = revOrderSeams2.reverse

    	println("drawing vertical removal seams on image")
        /*for testing:  println("final img size is " + finalImg.getWidth() + ", " + finalImg.getHeight() + 
         * "; dimensions of original " + imgCopy.getWidth() + ", " + imgCopy.getHeight() +
		"; vertical inserts: " + verticalSeams.length + " and horizontal: " + horizontalSeams.length)*/
		
		
    	//draw vertical seams on image and hold array of files showing the process
		val (seamVertDrawing, seamVertPic) = drawSeamsImage(imgCopy, verticalSeams, finalImg.getHeight(), 
		      finalImg.getWidth(), Color.BLACK, Utils.ImgPosition.Center)
	
	      //get seam map version of image with seams drawn on it
		  val bogusVertEmap : EnergyMap = new EnergyMap(Array.fill(seamVertPic.getHeight(), seamVertPic.getWidth())(0.0))
		  val vertGraphWithSeams = new SeamMap(bogusVertEmap, seamVertPic)

    	  println("inserting seams")

		  //get files of seams being removed
		  val (vertInsertGraph, vertSeamInsert) = showSeamRemoval(vertGraphWithSeams, verticalSeams, 
		      Color.BLACK, Utils.ImgPosition.Center, finalImg.getHeight(), finalImg.getWidth(), true)
		      
	      println("drawing horizontal removal seams on image")

      	//draw vertical seams on image and hold array of files showing the process
		val (seamHorzDrawing, seamHorzPic) = drawSeamsImage(vertInsertGraph.getImage, horizontalSeams, finalImg.getHeight(), 
		      finalImg.getWidth(), Color.BLACK, Utils.ImgPosition.Center)
	
	      //get seam map version of image with seams drawn on it
		  val bogusHorzEmap : EnergyMap = new EnergyMap(Array.fill(seamHorzPic.getHeight(), seamHorzPic.getWidth())(0.0))
		  val horzGraphWithSeams = new SeamMap(bogusHorzEmap, seamHorzPic)

    	  println("inserting seams")
                	  
		  //get files of seams being removed
		  val (horzInsertGraph, horzSeamInsert) = showSeamRemoval(horzGraphWithSeams, horizontalSeams, Color.BLACK, Utils.ImgPosition.Center,
		      finalImg.getHeight(), finalImg.getWidth(), true)
		      
		  val merge = Utils.generateFadeInImages(horzInsertGraph.getImage, finalImg, 40)

		      
		  //combine seam finding images with seam removal images
		  Utils.combineArrays(
		      newEnergyPics,
		      seamVertDrawing,
		      vertSeamInsert,
		      seamHorzDrawing,
		      horzSeamInsert,
		      merge,
		      finalImgFiles
		  )
        
        
      } 
      else {
    	  val seams = revOrderSeams.reverse

    	  println("drawing seams on image")
    	  //draw seams on image and hold array of files showing the process
		  val (seamDrawing, seampic) = drawSeamsImage(imgCopy, seams)
	
	      //get seam map version of image with seams drawn on it
		  val graphWithSeams = new SeamMap(emap, seampic)
	
		  //get files of seams being removed
      	  println("removing seams")
		  val (_, seamRemoval) = showSeamRemoval(graphWithSeams, seams, Color.BLACK, Utils.ImgPosition.Center,
		      img.getWidth(), img.getHeight(), false)

		      
		  //combine seam finding images with seam removal images
		  Utils.combineArrays(
		      energyPics,
		      seamDrawing,
		      seamRemoval,
		      Utils.generateLots(
		          Utils.imageToTempFile(
		        	Utils.giveEdges(getImage, Color.black, img.getHeight(), img.getWidth(), Utils.ImgPosition.Center)), 60)
		  )
		}
	}
	

	/**
	 * get image files of seams being removed or inserted
	 * @param graphWSeams			seamMap with seams drawn on it
	 * @param seams					seams to be removed / inserted
	 * @param background			background color in images
	 * @param placement				where the image should be placed on the background
	 * @param largestWidth			the width where the image is the largest
	 * @param largestHeight			the height where the image is the largest
	 * @param insertSeam			whether or not seam should be inserted or removed
	 * @return						the graph of the image after removal/insertion and the array of image files that resulted
	 */
	private def showSeamRemoval(graphWSeams: SeamMap, seams : List[SeamNode], background : Color, 
	    placement : Utils.ImgPosition, largestWidth : Int, largestHeight : Int, insertSeam : Boolean) : (SeamMap, Array[File]) = {
		  //remove seams, get image, add to array
		  seams.foldLeft( (graphWSeams, Array[File]() ) ) {
		    (graphAndArray, seam) =>
		      //holds on to the graph and the array of image files
		      val (oldGraph, theArray) =  graphAndArray
		      
		      //get new graph
		      val newGraph = 
		        if (insertSeam)
		        	oldGraph.insertNodes(seam::Nil)
	        	else
	        		oldGraph.deleteNodes(seam)
		      
		      //add image to utils
		      (newGraph,
		        	Utils.combineArrays(theArray,
		        		Array[File](
		            		Utils.imageToTempFile(
		            		    Utils.giveEdges(newGraph.getImage, background,
		            		        largestHeight, largestWidth, placement)))))
		  }
	}
	
	/**
	 * takes an image and draws seams in red on the image
	 * @param img				the buffered image to draw on
	 * @param seams				the seams to draw
	 * @return					the file pointers and the image with seams drawn on it
	 */
	private def drawSeamsImage(img: BufferedImage, seams : List[SeamNode]) : (Array[File], BufferedImage) = {
		    seams.foldLeft((Array[File](), img)) {
		        (arrAndImage, seam) => 
		          	//holds file image array and the current image
		        	val (curArray, curImage) = arrAndImage
	
			        //get image with seam drawn on it
			        val nextImage = drawSeamNodes(curImage, seam, (Color.red).getRGB())
			        val tmpFile = Utils.imageToTempFile(nextImage)
			        
			        //concat files
			        (Utils.combineArrays(curArray, Array(tmpFile)), nextImage)
	      	}	  
	}
	
	
	/**
	 * takes an image and draws seams in red on the image; this one provides edges given height and width max
	 * @param img				the buffered image to draw on
	 * @param seams				the seams to draw
	 * @param height			the images' height
	 * @param width				the images' width
	 * @param background		the background color
	 * @param placement			the placement of the image
	 * @return					the file pointers and the image with seams drawn on it
	 */
	private def drawSeamsImage(img: BufferedImage, seams : List[SeamNode], height : Int, width : Int, 
	    background : Color, placement : Utils.ImgPosition) : (Array[File], BufferedImage) = {
		    seams.foldLeft((Array[File](), img)) {
		        (arrAndImage, seam) => 
		          	//holds file image array and the current image
		        	val (curArray, curImage) = arrAndImage
	
			        //get image with seam drawn on it
			        val nextImage = drawSeamNodes(curImage, seam, (Color.red).getRGB())
			        
			        val tmpFile = Utils.imageToTempFile(Utils.giveEdges(nextImage, background,
		            		        height, width, placement))
			        
			        //concat files
			        (Utils.combineArrays(curArray, Array(tmpFile)), nextImage)
	      	}	  
	}
	
	
	
	/**
	 * generates new image copy from old
	 * @param img 		old image
	 * @return 			copy
	 */
	private def copyImage(img:BufferedImage) : BufferedImage = {
		val newImg = new BufferedImage(img.getWidth, img.getHeight, BufferedImage.TYPE_3BYTE_BGR)
		
		val g = newImg.createGraphics
		g.drawImage(img,0,0,null)
		
		newImg
	}
	
	/**
	 * draws a color for node given on image argument
	 * @param img			the image used
	 * @param node			the node whose x,y coordinates are used to draw on the image
	 * @param color			the color in which to write
	 * @return				the drawn upon buffered image
	 */
	private def drawSeamNodes(img:BufferedImage, node:SeamNode, color:Int) : BufferedImage = {
	  img.setRGB(node.thisItem.x, node.thisItem.y, color)
	  node.prev match {
	    case (prev : SeamNode) => drawSeamNodes(img, prev, color)
	    case _ => img
	  }
	}
	
	/**
	 * gets an image with seams drawn on it
	 * @return 			the drawn upon buffered image (drawn in red)
	 */
	def getSeamImage : BufferedImage = {
	   if (imageEnlarge) throw new IllegalArgumentException("getSeamImage does not work with image enlargement")
	  revOrderSeams.foldLeft(copyImage(img)) { (img, seam) => drawSeamNodes(img, seam, (Color.red).getRGB()) }
	}
	
	
	/**
	 * gets the GetEnergy object associated with the image
	 * @return		the GetEnergy object associated with an image
	 */	
	def getEnergyGetter : GetEnergy = { eget }
}